#pragma once

#include "Puntero.h"
#include "ICiudad.h"
#include "Ciudad.h"
#include "ITabla.h"
#include "Conexion.h"
#include "NodoConexion.h"
#include "Matriz.h"
#include "TablaHash.h"
#include "Iterador.h"
#include "ILista.h"
#include "ListaSimple.h"
#include "Tupla.h"
#include "TipoRetorno.h"
#include "NodoBusquedaDijkstra.h"
#include "ValoresDijktra.h"


class GrafoCiudad
{
public:
	
	GrafoCiudad(nat largo, Puntero<Comparador<Puntero<ICiudad>>> comparadorCuidades);
	~GrafoCiudad(){}

	/* agrega un cuidad al grafo */
	void AgregarVertice(const Puntero<ICiudad> &cuidad) ;

	/* borra una cuidad del grafo */
	//void BorrarVertice(const Puntero<ICiudad> &cuidad) ;

	/* agrega un arco entre dos cuidades */
	void AgregarArco(const Puntero<ICiudad> &cuidad1, const Puntero<ICiudad> &cuidad2, const Puntero<Conexion>& arco) ;

	/* retorna la cantidad de vertices del grafo */
	int CantidadVertices() const ;

	/* retorna la cantidad de arcos del grafo */
	int CantidadArcos() const ;
		
	/* retorna true si la cuidad pertenece al grafo */
	bool ExisteVertice(const Puntero<ICiudad> &cuidad) const ;

	
	/* retorna true si el grafo esta lleno */
	bool EstaLleno() const ;

	/* retorna true si el grafo esta vacio */
	bool EstaVacio() const ;

	const Puntero<Conexion>& ObtenerArcoAux(const Puntero<ICiudad> &cuidad1, const Puntero<ICiudad> &cuidad2) const ;

	void ActualizarMatrizCaminos();

	bool ExisteCamino(const Puntero<ICiudad> &ciudadO, const Puntero<ICiudad> &ciudadD) const;

	Puntero<Tupla<TipoRetorno,int, TipoTransporte, Iterador<pCiudad>>> RecorridoMasBarato(const Puntero<ICiudad> &ciudadO, const Puntero<ICiudad> &ciudadD);
	
	void ReccoridoMasBaratoConIter(const Puntero<ListaSimple<Puntero<Ciudad>>> listaIter);

	/*Tupla<TipoRetorno, Iterador<pCiudad>> TrayectoriaMenorDistancia(Iterador<Puntero<ICiudad>> iterCiudadesNoDeseadas,
		TipoTransporte tipoTransporte,Puntero<ICiudad> origen, Puntero<Ciudad> destino, int tiempoMax);
		*/

private:
	
	Array<Puntero<ICiudad>> vertices;
	Puntero<ITabla<Puntero<ICiudad>,int>> posiciones;
									
	Matriz<Puntero<ListaSimple<Puntero<Conexion>>>> matriz;
	int tope;
	int cantArcos;
	int cantVertices;
	int largo;
	
	//Esta lista almacena una unica conexion con toda la cantidad de omnibus y avoines
	//Me arroro O(n) en recorrer la matriz preguntando por cada una de sus conexiones en la lista
	Matriz<Puntero<Conexion>> matrizAux;
		
	void initMatrizAux(){
	
		for(int i=0;i<largo;i++)
		{		
			for(int j=0;j<largo;j++)
			{			
				this->matrizAux[i][j] = new Conexion();
			}
			
		}
	}
	//Fin Matriz AUX

	Matriz<bool> matrizCaminos;

	//Init false matriz de caminos
	void InitMatrizCaminos()

		{
		for(int i=0;i<largo;i++)
		{
			for(int j=0;j<largo;j++)
			{
				this->matrizCaminos[i][j] = false;
			}
	
		}

	}

	
	//Esto lo que hace es sumarme la cantidad de omnibus y aviones en un solo nodo Conexion
	void actualizarMatrizAux(int posCiudadOrigen, int posCiudadDestino, const Puntero<Conexion>& arco)
	{
		if(this->matrizAux[posCiudadOrigen][posCiudadDestino] != NULL)
		{
			Puntero<Conexion> con = matrizAux[posCiudadOrigen][posCiudadDestino];
			con->aviones += arco->aviones;
			con->omnibus += arco->omnibus;
			
			//Me llego una mejor distancia
			if(arco->distancia < con->distancia)
				con->distancia = arco->distancia;
			
			//Me llego mejor costo por avion
			if(arco->costoAvion < con->costoAvion)
				con->costoAvion = arco->costoAvion;
			
			//Me llego mejor costo por omnibus
			if(arco->costoOmnibus < con->costoOmnibus)
				con->costoOmnibus = arco->costoOmnibus;
			
		}

	}


	//estructuras auxiliares para algoritmo dijkstra

	int INF;//representa infinito para Dijkstra
	Array<Puntero<NodoBusquedaDijkstra>> nodosBusquedaAux;
	Array<bool> verticeHabilitado;
	

	// incializa los elementos que utiliza Dijkstr en su algoritmo
	void IniciarDijkstra()
	{
		INF = 50000;
		nodosBusquedaAux = Array<Puntero<NodoBusquedaDijkstra>>(this->tope);
		for(int i=0; i<this->tope; i++)
		{
			nodosBusquedaAux[i] = new NodoBusquedaDijkstra();
			nodosBusquedaAux[i]->anterior = 0;
			Puntero<ValoresDijktra> valores = new ValoresDijktra();
			valores->costo = INF;
			valores->distancia = INF;
			valores->tipo = Avion;
			nodosBusquedaAux[i]->valores = valores;
			nodosBusquedaAux[i]->conocido = false;
		}
	}
	
	//metodo auxiliar para algoritmo de Dijkstra
	//Devuelve la posicion del elemento no conocido de menor distancia
	int VerticeNoConocidoMenorCosto()
	{
		int min = INF+1;
		int posMin;
		
		for(int i=0; i<tope;i++)
		{
			if(nodosBusquedaAux[i]->valores->costo<min && !nodosBusquedaAux[i]->conocido && this->verticeHabilitado[i])
			{
				min = nodosBusquedaAux[i]->valores->costo;
				posMin = i;
			}
		}
		return posMin;
	}

	int VerticeNoConocidoMenorDistancia()
	{
		int min = INF+1;
		int posMin;
		
		for(int i=0; i<tope;i++)
		{
			if(nodosBusquedaAux[i]->valores->distancia<min && !nodosBusquedaAux[i]->conocido && this->verticeHabilitado[i])
			{
				min = nodosBusquedaAux[i]->valores->distancia;
				posMin = i;
			}
		}
		return posMin;
	}

	//Creo q no necesito esto
	nat ObtenerMenorCosto(int posF, int posC){
	
		Puntero<ListaSimple<Puntero<Conexion>>> listaEnPos = matriz[posF][posC];
		
		return 0;
	
	}

	bool ExisteCamino(int nodoDestino)
	{
		return nodosBusquedaAux[nodoDestino]->valores->costo!=INF;
	}

	void Dijkstra(int nodoOrigen, TipoTransporte tipoTransporte)
	{
		IniciarDijkstra();
		nodosBusquedaAux[nodoOrigen]->valores->costo = 0;
		int v;
		for(int i=0; i<this->tope; i++)
		{
			v = VerticeNoConocidoMenorDistancia();
			nodosBusquedaAux[v]->conocido = true;
			for(int w=0; w<this->tope; w++)
			{
				if(this->matriz[v][w] != NULL && !nodosBusquedaAux[w]->conocido)
				{
					bool avion = false;
					int costoAux; 
					int costo; 
					

					/*if(matrizAux[v][w]->costoAvion > matrizAux[v][w]->costoOmnibus)
						costoAux = matrizAux[v][w]->costoOmnibus;
					else{
						avion=true;
						costoAux = matrizAux[v][w]->costoAvion;
					}*/
					costoAux = matrizAux[v][w]->distancia;
					
					if(matrizAux[v][w]->costoAvion > matrizAux[v][w]->costoOmnibus)
						costo = matrizAux[v][w]->costoOmnibus;
					else{
						avion=true;
						costo = matrizAux[v][w]->costoAvion;
					}


					if((nodosBusquedaAux[v]->valores->distancia + costoAux) < nodosBusquedaAux[w]->valores->distancia)
					{
						nodosBusquedaAux[w]->valores->distancia = nodosBusquedaAux[v]->valores->distancia + costoAux;
						nodosBusquedaAux[w]->anterior = v;
						nodosBusquedaAux[w]->valores->costo = nodosBusquedaAux[w]->valores->costo + costo;
						
						if(avion)
							nodosBusquedaAux[w]->valores->tipo = Avion;
						else
							nodosBusquedaAux[w]->valores->tipo = Omnibus;
						
						nodosBusquedaAux[w]->valores->costo = costo;

					}   
				}
			}
		}
	}


	int CantidadDeTramos(int nodoOrigen, int nodoDestino)
	{
		int nodoActual = nodoDestino;
		int cantidad = 0;
		while(nodoActual != nodoOrigen)
		{
			nodoActual = nodosBusquedaAux[nodoActual]->anterior;
			cantidad++;
		}
		return cantidad;
	}
	
	int ObtenerCostoDijkstra(int nodoDestino)
	{
		return nodosBusquedaAux[nodoDestino]->valores->costo;
	}

	Array<Puntero<ICiudad>> ObtenerCiudadesCaminoMasCorto(int nodoOrigen, int nodoDestino, int largoCamino)
	{
		Array<Puntero<ICiudad>> arregloAux(largoCamino);
		Puntero<ListaSimple<Tupla<pCiudad, TipoTransporte, nat, nat>>> itinerario = new ListaSimple<Tupla<pCiudad, TipoTransporte, nat, nat>>();

		int nodoActual = nodoDestino;
		
		int i = 0;
		while(nodoActual != nodoOrigen)
		{
			arregloAux[i] = this->vertices[nodoActual];
			nodoActual = nodosBusquedaAux[nodoActual]->anterior;
			i++;
		}
		arregloAux[i] = this->vertices[nodoActual];

		Array<Puntero<ICiudad>> retorno(largoCamino);
		int j = 0;
		for(int i = largoCamino-1; i>=0; i--)
		{
			retorno[j] = arregloAux[i];
			j++;
		}

		return retorno;
	}


};